package leetcode_800;

/**
 *@author 周杨
 *MaxChunksToMakeSorted_769 求给一个数组分块 每个快里的元素大小都不超过Index
 *describe:循环遍历 确定窗口大小即可 AC 100%
 *2018年10月19日 下午1:16:43
 */
public class MaxChunksToMakeSorted_769 {
	
	public static void main(String[] args) {
		MaxChunksToMakeSorted_769 test=new MaxChunksToMakeSorted_769();
		System.out.println(test.maxChunksToSorted(new int[] {1,2,0,3}));
		System.out.println(test.maxChunksToSorted(new int[] {4,3,2,1,0}));
		System.out.println(test.maxChunksToSorted(new int[] {1,0,2,3,4}));
		System.out.println(test.maxChunksToSorted(new int[] {2,1,3,4,4}));
	}
	
	public int maxChunksToSorted(int[] arr) {
	      if(arr.length==1)
				return 1;
        int res=0,left=0,right=arr[0];
        while(left<arr.length) {
        	while(left<=right) {
        		if(arr[left]>right) {
        			right=arr[left];
        			++left;
        			continue;
        		}
        		++left;
        	}//退出来就是此区间已经遍历完
        	if(left==arr.length)
        		return res+1;
        	right=arr[left];
        	res++;
        }
        return res+1;
    }
}
